/**
 * 【动态规划】背包问题
 * @param {Array<Number>} weights 
 * @param {Array<Number>} values 
 * @param {Number} capacity 
 * @returns 
 */
export const knapSack = (weights, values, capacity) => {
    // 定义一个矩阵用于存放每一种重量下能够放下物品的最大价值
    // 矩阵的 *列* 代表着背包的最大容量
    // 矩阵的 *行* 代表着当前想要放入的物品
    const matrix = [[]]

    // 第一轮遍历：初始化放入第一个物品，在不同背包容量的情况下，背包里物品的价值情况
    for (let j = 0; j <= capacity; j++) {
        // 如果想要放入的物品比当前背包容量要重
        if (weights[0] > j) {
            // 背包啥也放不下去，背包内没有物品，没有价值
            matrix[0][j] = 0
        } else[
            // 如果放入物品比背包容量要轻，直接把这个物品放进去，该背包在当前容量下最大价值就是放入第一个物品的价值
            matrix[0][j] = values[0]
        ]
    }

    // 第二轮遍历：开始放入第二个及以后的物品。
    for (let i = 1; i < weights.length; i++) {
        // 初始化矩阵行，用于存放当前物品想要放入情况下，背包的价值情况
        if (!matrix[i]) {
            matrix[i] = []
        }
        // 开始遍历背包在每一个容量下，放下货物的最大价值情况
        for (let j = 0; j <= capacity; j++) {
            // 当想要放的货物的重量比背包的容量还大，放不下，当前能放下货物的最大价值和不放这个货物的最大价值情况相同
            if (j < weights[i]) {
                matrix[i][j] = matrix[i - 1][j]
            } else {
                // 当想要放的货物重量背包能放下，则开始比较
                // 不放这个物品的最大货物价值 与 放下这个物品并且再放剩余容量可以放下物品的最大价值之和
                // 取大者为此时容量背包的最大价值
                matrix[i][j] = Math.max(matrix[i - 1][j], matrix[i - 1][j - weights[i]] + values[i])
            }
        }
    }

    console.log(matrix)
    // 背包可以放下物品的最大价值为举证的最右下角那个值
    return matrix[weights.length - 1][capacity]
}